//给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。 
// 如果可以，返回 true ；否则返回 false 。
// magazine 中的每个字符只能在 ransomNote 中使用一次。
// 示例 1：
//输入：ransomNote = "a", magazine = "b"
//输出：false
// 示例 2：
//输入：ransomNote = "aa", magazine = "ab"
//输出：false
// 示例 3：
//输入：ransomNote = "aa", magazine = "aab"
//输出：true
// 提示：
// 1 <= ransomNote.length, magazine.length <= 10⁵
// ransomNote 和 magazine 由小写英文字母组成 
// Related Topics 哈希表 字符串 计数 👍 292 👎 0

package leetcode.editor.cn;

class RansomNote {
    public static void main(String[] args) {
        Solution solution = new RansomNote().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /*
        public boolean canConstruct(String ransomNote, String magazine) {
            char[] record = new char[26];
            // 映射在hash表中
            for (int i = 0; i < ransomNote.length(); i++) {
                record[ransomNote.charAt(i) - 'a']++;
            }
            // 遍历magazine，在hash表中查找是否存在
            for (int i = 0; i < magazine.length(); i++) {
                // 先判断数组中是否为0，不为0则在ransomNote中存在
                if (record[magazine.charAt(i) - 'a'] != 0) {
                    record[magazine.charAt(i) - 'a']--;
                }
            }
            // 都为0，则可以表示
            for (int i = 0; i < record.length; i++) {
                if (record[i] != 0) {
                    return false;
                }
            }
            return true;
        }
         */
        public boolean canConstruct(String ransomNote, String magazine) {
            char[] record = new char[26];
            for (int i = 0; i < magazine.length(); i++) {
                // 通过recode数据记录 magazine里各个字符出现次数
                record[magazine.charAt(i) - 'a']++;
            }
            // 遍历ransomNote
            for (int i = 0; i < ransomNote.length(); i++) {
                // 对于金信中的每一个字符都在数组中查找
                // 找到相应位减一，否则找不到返回false
                if (record[ransomNote.charAt(i) - 'a'] > 0) {
                    record[ransomNote.charAt(i) - 'a']--;
                }else {
                    return false;
                }
            }
            return true;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
